package com.tgy.algorithm.base._动态规划;

/**
 * 跳马问题：
 * 把象棋棋盘放在第一象限位置，棋盘的最左下角位置是(0,0),那么整个棋盘就是横坐标上九条线，纵坐标上十条线的区域
 * 给定三个参数，x,y,k
 * 返回马从（0，0）位置出发，必须走K步，最后落在（x,y）上的方法数有多少个。
 */
public class _象棋马跳日问题 {


    public static int getXQHourse(int x,int y,int k) {

        // 走到最后了
        if (k == 0) {
            return x == 0 && y == 0 ?1:0;
        }

        /**
         *  x 0-8
         *  y 0-9
         */
        if (x < 0 || x > 8 || y < 0 || y > 9) {
            return 0;
        }

        int ret = 0;

        ret = getXQHourse(x+1,y-2,k-1) + getXQHourse(x+2,y-1,k-1)
                + getXQHourse(x+2,y+1,k-1) + getXQHourse(x+1,y+2,k-1)
                + getXQHourse(x-1,y+2,k-1) + getXQHourse(x-2,y+1,k-1)
                + getXQHourse(x-2,y-1,k-1) + getXQHourse(x-1,y-2,k-1);

        return ret;
    }

    public static int getXQHourse01(int x,int y, int k) {

        int[][][] dp = new int[9][10][k+1];
        dp[0][0][0] = 1;

        for (int l = 1; l <= k; l++) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 10; j++) {
                    dp[i][j][l] = getOtherHourse(dp,i+1,j-2,l-1) + getOtherHourse(dp,i+2,j-1,l-1)
                            + getOtherHourse(dp,i+2,j+1,l-1) + getOtherHourse(dp,i+1,j+2,l-1)
                            + getOtherHourse(dp,i-1,j+2,l-1) + getOtherHourse(dp,i-2,j+1,l-1)
                            + getOtherHourse(dp,i-2,j-1,l-1) + getOtherHourse(dp,i-1,j-2,l-1)
                    ;
                }
            }
        }

        return dp[x][y][k];
    }

    public static int getOtherHourse(int[][][] nums,int x,int y,int k) {
        if (x < 0 || x > 8 || y < 0 || y > 9) {
            return 0;
        }

        return nums[x][y][k];
    }

    public static void main(String[] args) {

        int xqHourse = getXQHourse(2, 3, 3);
        int xqHourse01 = getXQHourse01(2, 3, 3);
        System.out.println(xqHourse);
        System.out.println(xqHourse01);
    }
}
